[Coding036] LeetCode 83

Remove Duplicates from Sorted List

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

• 本题虽然看上去简单，但是思路却需要十分清晰才能明白其中的逻辑。

• 是一道很不错的题目！

题目：83. Remove Duplicates from Sorted List

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1:

xxxxxxxxxx
2
1
Input: head = [1,1,2]
2
Output: [1,2]

Example 2:

xxxxxxxxxx
2
1
Input: head = [1,1,2,3,3]
2
Output: [1,2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].

• -100 <= Node.val <= 100

• The list is guaranteed to be sorted in ascending order.

代码1

xxxxxxxxxx
38
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode deleteDuplicates(ListNode head) {
13

14
        if (head == null || head.next == null)
15
            return head;
16
        
17
        ListNode dummy = new ListNode(0);
18
        dummy.next = head;
19

20
        ListNode p = dummy;
21

22
        while (p.next != null && p.next.next != null)
23
        {
24
            ListNode q = p.next;
25
            if (p.next.val == q.next.val)
26
            {
27
                p.next = q.next;
28
                p = p.next;  // 这句代码不能要。因为还存在这种情况：[1, 1, 1]
29
            }
30
            else
31
            {
32
                p = p.next;
33
            }
34
        }
35

36
        return dummy.next;
37
    }
38
}

代码解读 | 评价

• 特殊情况需要特别注意！

复杂度分析

代码2

比代码1看上去更清爽。

xxxxxxxxxx
24
1
class Solution {
2
    public ListNode deleteDuplicates(ListNode head) {
3
        ListNode dummy = new ListNode(-101);
4
        
5
        dummy.next = head;
6
        
7
        ListNode p = dummy;
8
        
9
        while (p.next != null)
10
        {
11
            ListNode q = p.next;
12
            if (p.val != q.val)
13
            {
14
                p = q;
15
            }
16
            else
17
            {
18
                p.next = q.next;
19
            }
20
        }
21
        
22
        return dummy.next;
23
    }
24
}